![Streebog-preview](assets/1.png)
Как и планировалось, следом за реализацией семейства хэш-функций SHA, появляется Стрибог и тоже в двух версиях, для 256 и 512 бит на выходе. Надеюсь эта статья будет полезна другим студентам. Более опытные разработчики в комментариях приветствуются.

Весь код сохранен в [репозитории GitVerse](https://gitverse.ru/digit4lsh4d0w/cryptography/content/main/hand-made-streebog). Есть обсуждение на [Habr](https://habr.com/ru/articles/816011/).

Прошлая статья ["Реализация SHA256 и SHA512 на языке RUST"](https://habr.com/ru/articles/811639/) очень сильно помогла мне в понимании работы SHA, кроме того в комментариях нашлись поистине полезные советы, спасибо за это!

В основе Стрибог лежат 5 простейших функций:

![Операции](assets/2.png)

1.  Сложение двух 512 битных чисел.
2.  X-преобразование.
3.  S-преобразование.
4.  P-преобразование.
5.  L-преобразование.

Из этих функций строятся:

1.  Функция вычисления раундовых ключей.
2.  E-преобразование.
3.  Функция сжатия g.
4.  Общая функция вычисления хэш-суммы.

# Сложение двух 512 битных чисел

Как следует из заголовка - необходимо иметь функцию, которая складывает длинные числа, при этом возможное переполнение будет отбрасываться. Так как планируется, что эти два числа `a` и `b` мы имеем в виде массивов байт, то и алгоритм будет соответствующий.

Делается это довольно просто, мы берем соответствующие байты из `a` и `b`, представляем их в качестве двухбайтовых чисел и складываем.

![Увеличение размера](assets/3.png)
Приведение типов

![Сложение](assets/4.png)
Сложение

Возможное переполнение будет учитываться, поскольку мы представили оба числа как двухбайтовые. Переполнение как раз будет храниться во втором байте результирующего числа.

Мы снова делаем приведение типов и кладем младший байт результирующего числа в массив результата `result`.

На следующей итерации мы делаем все то же самое, но не забываем учесть переполнение, просто сдвигаем результат предыдущего сложения на один байт и добавляем к результату сложения `a` и `b`.

![Вторая итерация](assets/5.png)
Вторая итерация

Не забываем, что необходимо складывать начиная с младших байт, то есть с конца массивов.

```rust
fn add_512(a: &[u8; 64], b: &[u8; 64], result: &mut [u8; 64]) {
    let mut temp: u16 = 0;
    for i in (0..64).rev() {
        temp = a[i] as u16 + b[i] as u16 + (temp >> 8);
        result[i] = temp as u8;
    }
}
```

# Четыре преобразования

Стрибог использует четыре простые функции: `X`, `S`, `P`, `L`.

## X-преобразование

Это простая операция `XOR` над 512 битными числами. Так же, как и при сложении 512 битных чисел, мы будем перебирать байты входящих массивов `a` и `b`, а результат `XOR` будет укладываться в `result`.

![Пример операции X](assets/6.png)
Пример операции X

Код:

```rust
fn transform_x(a: &[u8; 64], b: &[u8; 64], result: &mut [u8; 64]) {
    for (index, byte) in result.iter_mut().enumerate() {
        *byte = a[index] ^ b[index];
    }
}
```

## S-преобразование

Это тоже довольно простое преобразование. Мы перебираем каждый байт входящего массива `result` и заменяем на тот, что находится в массиве `PI` под номером, на который этот байт указывает.

![S преобразование](assets/7.png)

![Пример операции S](assets/8.png)
Пример операции S

Константы:
```rust
pub const PI: [u8; 256] = [
    0xfc, 0xee, 0xdd, 0x11, 0xcf, 0x6e, 0x31, 0x16, 0xfb, 0xc4, 0xfa, 0xda, 0x23, 0xc5, 0x04, 0x4d,
    0xe9, 0x77, 0xf0, 0xdb, 0x93, 0x2e, 0x99, 0xba, 0x17, 0x36, 0xf1, 0xbb, 0x14, 0xcd, 0x5f, 0xc1,
    0xf9, 0x18, 0x65, 0x5a, 0xe2, 0x5c, 0xef, 0x21, 0x81, 0x1c, 0x3c, 0x42, 0x8b, 0x01, 0x8e, 0x4f,
    0x05, 0x84, 0x02, 0xae, 0xe3, 0x6a, 0x8f, 0xa0, 0x06, 0x0b, 0xed, 0x98, 0x7f, 0xd4, 0xd3, 0x1f,
    0xeb, 0x34, 0x2c, 0x51, 0xea, 0xc8, 0x48, 0xab, 0xf2, 0x2a, 0x68, 0xa2, 0xfd, 0x3a, 0xce, 0xcc,
    0xb5, 0x70, 0x0e, 0x56, 0x08, 0x0c, 0x76, 0x12, 0xbf, 0x72, 0x13, 0x47, 0x9c, 0xb7, 0x5d, 0x87,
    0x15, 0xa1, 0x96, 0x29, 0x10, 0x7b, 0x9a, 0xc7, 0xf3, 0x91, 0x78, 0x6f, 0x9d, 0x9e, 0xb2, 0xb1,
    0x32, 0x75, 0x19, 0x3d, 0xff, 0x35, 0x8a, 0x7e, 0x6d, 0x54, 0xc6, 0x80, 0xc3, 0xbd, 0x0d, 0x57,
    0xdf, 0xf5, 0x24, 0xa9, 0x3e, 0xa8, 0x43, 0xc9, 0xd7, 0x79, 0xd6, 0xf6, 0x7c, 0x22, 0xb9, 0x03,
    0xe0, 0x0f, 0xec, 0xde, 0x7a, 0x94, 0xb0, 0xbc, 0xdc, 0xe8, 0x28, 0x50, 0x4e, 0x33, 0x0a, 0x4a,
    0xa7, 0x97, 0x60, 0x73, 0x1e, 0x00, 0x62, 0x44, 0x1a, 0xb8, 0x38, 0x82, 0x64, 0x9f, 0x26, 0x41,
    0xad, 0x45, 0x46, 0x92, 0x27, 0x5e, 0x55, 0x2f, 0x8c, 0xa3, 0xa5, 0x7d, 0x69, 0xd5, 0x95, 0x3b,
    0x07, 0x58, 0xb3, 0x40, 0x86, 0xac, 0x1d, 0xf7, 0x30, 0x37, 0x6b, 0xe4, 0x88, 0xd9, 0xe7, 0x89,
    0xe1, 0x1b, 0x83, 0x49, 0x4c, 0x3f, 0xf8, 0xfe, 0x8d, 0x53, 0xaa, 0x90, 0xca, 0xd8, 0x85, 0x61,
    0x20, 0x71, 0x67, 0xa4, 0x2d, 0x2b, 0x09, 0x5b, 0xcb, 0x9b, 0x25, 0xd0, 0xbe, 0xe5, 0x6c, 0x52,
    0x59, 0xa6, 0x74, 0xd2, 0xe6, 0xf4, 0xb4, 0xc0, 0xd1, 0x66, 0xaf, 0xc2, 0x39, 0x4b, 0x63, 0xb6,
];
```

Код:
```rust
fn transform_s(result: &mut [u8; 64]) {
    result.iter_mut().for_each(|byte| *byte = PI[*byte as usize]);
}
```

## P-преобразование

Это тоже довольно простое преобразование. Мы должны переставить байты из массива `result` в порядке, который задает массив `TAU`.

Так как мы в Rust не можем изменять и перебирать один и тот же объект одновременно, то предварительно нужно сделать копию массива `result`.

![Пример операции P](assets/9.png)
Пример операции P

Мы видим, что первый байт из левой части стал первым байтом правой части, а вот второй байт левой части стал восьмым байтом правой части, но этого на примере не видно.

Константы:
```rust
pub const TAU: [u8; 64] = [
    0x00, 0x08, 0x10, 0x18, 0x20, 0x28, 0x30, 0x38,
    0x01, 0x09, 0x11, 0x19, 0x21, 0x29, 0x31, 0x39,
    0x02, 0x0a, 0x12, 0x1a, 0x22, 0x2a, 0x32, 0x3a,
    0x03, 0x0b, 0x13, 0x1b, 0x23, 0x2b, 0x33, 0x3b,
    0x04, 0x0c, 0x14, 0x1c, 0x24, 0x2c, 0x34, 0x3c,
    0x05, 0x0d, 0x15, 0x1d, 0x25, 0x2d, 0x35, 0x3d,
    0x06, 0x0e, 0x16, 0x1e, 0x26, 0x2e, 0x36, 0x3e,
    0x07, 0x0f, 0x17, 0x1f, 0x27, 0x2f, 0x37, 0x3f,
];
```

Код:
```rust
fn transform_p(result: &mut [u8; 64]) {
    let temp = result.clone();
    for (index, position) in TAU.iter().enumerate() {
        result[index] = temp[*position as usize];
    }
}
```

## L-преобразование

А вот это уже чуть более сложное преобразование. На входе мы как всегда имеем 512 битное число `result`, которое состоит из 64 байт. Мы снова должны сделать приведение типов - склеить каждые 8 байт в одно число. Таким образом из входящих 64 чисел мы получим 8.

```rust
let input_u64: [u64; 8] = result.chunks_exact(8)
    .map(|bytes| u64::from_be_bytes(bytes.try_into().unwrap()))
    .collect::<Vec<u64>>()
    .try_into()
    .unwrap();
```

Начнем с первого. Всего в этом числе 64 бита, в то же время в массиве `A` 64 элемента. Мы будем перебирать биты первого числа и если встретим 1, то производим операцию `XOR` первого элемента массива `buffers` и элемента из `A`, который соответствует индексу бита. Важная особенность заключается в том, что первый элемент массива `A` находится "в конце", а последний "в начале".

```rust
for i in 0..8 {
    for j in 0..64 {
        if (input_u64[i] >> j) & 1 == 1 {
            buffers[i] ^= A[63 - j];
        }
    }
}
```

В конце не забываем обратно разделить 64 битные числа на байты.

```rust
let buffer: [u8; 64] = buffers.iter()
    .flat_map(|bytes| bytes.to_be_bytes())
    .collect::<Vec<u8>>()
    .try_into()
    .unwrap();
```

- Изначально массив `buffers` инициализирован нулями.
- Для удобства можно инвертировать порядок байт в `A`.

![Пример операции L](assets/10.png)
Пример операции L

Константы:

```rust
pub const A: [u64; 64] = [
    0x8e20faa72ba0b470, 0x47107ddd9b505a38, 0xad08b0e0c3282d1c, 0xd8045870ef14980e,
    0x6c022c38f90a4c07, 0x3601161cf205268d, 0x1b8e0b0e798c13c8, 0x83478b07b2468764,
    0xa011d380818e8f40, 0x5086e740ce47c920, 0x2843fd2067adea10, 0x14aff010bdd87508,
    0x0ad97808d06cb404, 0x05e23c0468365a02, 0x8c711e02341b2d01, 0x46b60f011a83988e,
    0x90dab52a387ae76f, 0x486dd4151c3dfdb9, 0x24b86a840e90f0d2, 0x125c354207487869,
    0x092e94218d243cba, 0x8a174a9ec8121e5d, 0x4585254f64090fa0, 0xaccc9ca9328a8950,
    0x9d4df05d5f661451, 0xc0a878a0a1330aa6, 0x60543c50de970553, 0x302a1e286fc58ca7,
    0x18150f14b9ec46dd, 0x0c84890ad27623e0, 0x0642ca05693b9f70, 0x0321658cba93c138,
    0x86275df09ce8aaa8, 0x439da0784e745554, 0xafc0503c273aa42a, 0xd960281e9d1d5215,
    0xe230140fc0802984, 0x71180a8960409a42, 0xb60c05ca30204d21, 0x5b068c651810a89e,
    0x456c34887a3805b9, 0xac361a443d1c8cd2, 0x561b0d22900e4669, 0x2b838811480723ba,
    0x9bcf4486248d9f5d, 0xc3e9224312c8c1a0, 0xeffa11af0964ee50, 0xf97d86d98a327728,
    0xe4fa2054a80b329c, 0x727d102a548b194e, 0x39b008152acb8227, 0x9258048415eb419d,
    0x492c024284fbaec0, 0xaa16012142f35760, 0x550b8e9e21f7a530, 0xa48b474f9ef5dc18,
    0x70a6a56e2440598e, 0x3853dc371220a247, 0x1ca76e95091051ad, 0x0edd37c48a08a6d8,
    0x07e095624504536c, 0x8d70c431ac02a736, 0xc83862965601dd1b, 0x641c314b2b8ee083,
];
```

Код:

```rust
fn transform_l(result: &mut [u8; 64]) {
    // Объединение 8 байт в одну последовательность
    let input_u64: [u64; 8] = result.chunks_exact(8)
        .map(|bytes| u64::from_be_bytes(bytes.try_into().unwrap()))
        .collect::<Vec<u64>>()
        .try_into()
        .unwrap();

    let mut buffers = [0u64; 8];

    for i in 0..8 {
        for j in 0..64 {
            if (input_u64[i] >> j) & 1 == 1 {
                buffers[i] ^= A[63 - j];
            }
        }
    }

    // Разделение модифицированной последовательности на части по 8 байт
    let buffer: [u8; 64] = buffers.iter()
        .flat_map(|bytes| bytes.to_be_bytes())
        .collect::<Vec<u8>>()
        .try_into()
        .unwrap();

    for (index, byte) in buffer.iter().enumerate() {
        result[index] = *byte;
    }
}
```

# Функция вычисления раундовых ключей

Теперь, когда у нас есть 4 простых преобразования, мы можем собрать из них функцию вычисления раундовых ключей. Для этого нам понадобятся новые итерационные константы `C`. Функция принимает массив ключей и индекс итерации. По очереди вызываются преобразования `X`, `S`, `P`, `L`.

![Генерация раундовых ключей](assets/11.png)

Константы:

```rust
pub const C: [[u8; 64]; 12] = [
    [
        0xb1, 0x08, 0x5b, 0xda, 0x1e, 0xca, 0xda, 0xe9, 0xeb, 0xcb, 0x2f, 0x81, 0xc0, 0x65, 0x7c, 0x1f,
        0x2f, 0x6a, 0x76, 0x43, 0x2e, 0x45, 0xd0, 0x16, 0x71, 0x4e, 0xb8, 0x8d, 0x75, 0x85, 0xc4, 0xfc,
        0x4b, 0x7c, 0xe0, 0x91, 0x92, 0x67, 0x69, 0x01, 0xa2, 0x42, 0x2a, 0x08, 0xa4, 0x60, 0xd3, 0x15,
        0x05, 0x76, 0x74, 0x36, 0xcc, 0x74, 0x4d, 0x23, 0xdd, 0x80, 0x65, 0x59, 0xf2, 0xa6, 0x45, 0x07,
    ],
    [
        0x6f, 0xa3, 0xb5, 0x8a, 0xa9, 0x9d, 0x2f, 0x1a, 0x4f, 0xe3, 0x9d, 0x46, 0x0f, 0x70, 0xb5, 0xd7,
        0xf3, 0xfe, 0xea, 0x72, 0x0a, 0x23, 0x2b, 0x98, 0x61, 0xd5, 0x5e, 0x0f, 0x16, 0xb5, 0x01, 0x31,
        0x9a, 0xb5, 0x17, 0x6b, 0x12, 0xd6, 0x99, 0x58, 0x5c, 0xb5, 0x61, 0xc2, 0xdb, 0x0a, 0xa7, 0xca,
        0x55, 0xdd, 0xa2, 0x1b, 0xd7, 0xcb, 0xcd, 0x56, 0xe6, 0x79, 0x04, 0x70, 0x21, 0xb1, 0x9b, 0xb7,
    ],
    [
        0xf5, 0x74, 0xdc, 0xac, 0x2b, 0xce, 0x2f, 0xc7, 0x0a, 0x39, 0xfc, 0x28, 0x6a, 0x3d, 0x84, 0x35,
        0x06, 0xf1, 0x5e, 0x5f, 0x52, 0x9c, 0x1f, 0x8b, 0xf2, 0xea, 0x75, 0x14, 0xb1, 0x29, 0x7b, 0x7b,
        0xd3, 0xe2, 0x0f, 0xe4, 0x90, 0x35, 0x9e, 0xb1, 0xc1, 0xc9, 0x3a, 0x37, 0x60, 0x62, 0xdb, 0x09,
        0xc2, 0xb6, 0xf4, 0x43, 0x86, 0x7a, 0xdb, 0x31, 0x99, 0x1e, 0x96, 0xf5, 0x0a, 0xba, 0x0a, 0xb2,
    ],
    [
        0xef, 0x1f, 0xdf, 0xb3, 0xe8, 0x15, 0x66, 0xd2, 0xf9, 0x48, 0xe1, 0xa0, 0x5d, 0x71, 0xe4, 0xdd,
        0x48, 0x8e, 0x85, 0x7e, 0x33, 0x5c, 0x3c, 0x7d, 0x9d, 0x72, 0x1c, 0xad, 0x68, 0x5e, 0x35, 0x3f,
        0xa9, 0xd7, 0x2c, 0x82, 0xed, 0x03, 0xd6, 0x75, 0xd8, 0xb7, 0x13, 0x33, 0x93, 0x52, 0x03, 0xbe,
        0x34, 0x53, 0xea, 0xa1, 0x93, 0xe8, 0x37, 0xf1, 0x22, 0x0c, 0xbe, 0xbc, 0x84, 0xe3, 0xd1, 0x2e,
    ],
    [
        0x4b, 0xea, 0x6b, 0xac, 0xad, 0x47, 0x47, 0x99, 0x9a, 0x3f, 0x41, 0x0c, 0x6c, 0xa9, 0x23, 0x63,
        0x7f, 0x15, 0x1c, 0x1f, 0x16, 0x86, 0x10, 0x4a, 0x35, 0x9e, 0x35, 0xd7, 0x80, 0x0f, 0xff, 0xbd,
        0xbf, 0xcd, 0x17, 0x47, 0x25, 0x3a, 0xf5, 0xa3, 0xdf, 0xff, 0x00, 0xb7, 0x23, 0x27, 0x1a, 0x16,
        0x7a, 0x56, 0xa2, 0x7e, 0xa9, 0xea, 0x63, 0xf5, 0x60, 0x17, 0x58, 0xfd, 0x7c, 0x6c, 0xfe, 0x57,
    ],
    [
        0xae, 0x4f, 0xae, 0xae, 0x1d, 0x3a, 0xd3, 0xd9, 0x6f, 0xa4, 0xc3, 0x3b, 0x7a, 0x30, 0x39, 0xc0,
        0x2d, 0x66, 0xc4, 0xf9, 0x51, 0x42, 0xa4, 0x6c, 0x18, 0x7f, 0x9a, 0xb4, 0x9a, 0xf0, 0x8e, 0xc6,
        0xcf, 0xfa, 0xa6, 0xb7, 0x1c, 0x9a, 0xb7, 0xb4, 0x0a, 0xf2, 0x1f, 0x66, 0xc2, 0xbe, 0xc6, 0xb6,
        0xbf, 0x71, 0xc5, 0x72, 0x36, 0x90, 0x4f, 0x35, 0xfa, 0x68, 0x40, 0x7a, 0x46, 0x64, 0x7d, 0x6e,
    ],
    [
        0xf4, 0xc7, 0x0e, 0x16, 0xee, 0xaa, 0xc5, 0xec, 0x51, 0xac, 0x86, 0xfe, 0xbf, 0x24, 0x09, 0x54,
        0x39, 0x9e, 0xc6, 0xc7, 0xe6, 0xbf, 0x87, 0xc9, 0xd3, 0x47, 0x3e, 0x33, 0x19, 0x7a, 0x93, 0xc9,
        0x09, 0x92, 0xab, 0xc5, 0x2d, 0x82, 0x2c, 0x37, 0x06, 0x47, 0x69, 0x83, 0x28, 0x4a, 0x05, 0x04,
        0x35, 0x17, 0x45, 0x4c, 0xa2, 0x3c, 0x4a, 0xf3, 0x88, 0x86, 0x56, 0x4d, 0x3a, 0x14, 0xd4, 0x93,
    ],
    [
        0x9b, 0x1f, 0x5b, 0x42, 0x4d, 0x93, 0xc9, 0xa7, 0x03, 0xe7, 0xaa, 0x02, 0x0c, 0x6e, 0x41, 0x41,
        0x4e, 0xb7, 0xf8, 0x71, 0x9c, 0x36, 0xde, 0x1e, 0x89, 0xb4, 0x44, 0x3b, 0x4d, 0xdb, 0xc4, 0x9a,
        0xf4, 0x89, 0x2b, 0xcb, 0x92, 0x9b, 0x06, 0x90, 0x69, 0xd1, 0x8d, 0x2b, 0xd1, 0xa5, 0xc4, 0x2f,
        0x36, 0xac, 0xc2, 0x35, 0x59, 0x51, 0xa8, 0xd9, 0xa4, 0x7f, 0x0d, 0xd4, 0xbf, 0x02, 0xe7, 0x1e,
    ],
    [
        0x37, 0x8f, 0x5a, 0x54, 0x16, 0x31, 0x22, 0x9b, 0x94, 0x4c, 0x9a, 0xd8, 0xec, 0x16, 0x5f, 0xde,
        0x3a, 0x7d, 0x3a, 0x1b, 0x25, 0x89, 0x42, 0x24, 0x3c, 0xd9, 0x55, 0xb7, 0xe0, 0x0d, 0x09, 0x84,
        0x80, 0x0a, 0x44, 0x0b, 0xdb, 0xb2, 0xce, 0xb1, 0x7b, 0x2b, 0x8a, 0x9a, 0xa6, 0x07, 0x9c, 0x54,
        0x0e, 0x38, 0xdc, 0x92, 0xcb, 0x1f, 0x2a, 0x60, 0x72, 0x61, 0x44, 0x51, 0x83, 0x23, 0x5a, 0xdb,
    ],
    [
        0xab, 0xbe, 0xde, 0xa6, 0x80, 0x05, 0x6f, 0x52, 0x38, 0x2a, 0xe5, 0x48, 0xb2, 0xe4, 0xf3, 0xf3,
        0x89, 0x41, 0xe7, 0x1c, 0xff, 0x8a, 0x78, 0xdb, 0x1f, 0xff, 0xe1, 0x8a, 0x1b, 0x33, 0x61, 0x03,
        0x9f, 0xe7, 0x67, 0x02, 0xaf, 0x69, 0x33, 0x4b, 0x7a, 0x1e, 0x6c, 0x30, 0x3b, 0x76, 0x52, 0xf4,
        0x36, 0x98, 0xfa, 0xd1, 0x15, 0x3b, 0xb6, 0xc3, 0x74, 0xb4, 0xc7, 0xfb, 0x98, 0x45, 0x9c, 0xed,
    ],
    [
        0x7b, 0xcd, 0x9e, 0xd0, 0xef, 0xc8, 0x89, 0xfb, 0x30, 0x02, 0xc6, 0xcd, 0x63, 0x5a, 0xfe, 0x94,
        0xd8, 0xfa, 0x6b, 0xbb, 0xeb, 0xab, 0x07, 0x61, 0x20, 0x01, 0x80, 0x21, 0x14, 0x84, 0x66, 0x79,
        0x8a, 0x1d, 0x71, 0xef, 0xea, 0x48, 0xb9, 0xca, 0xef, 0xba, 0xcd, 0x1d, 0x7d, 0x47, 0x6e, 0x98,
        0xde, 0xa2, 0x59, 0x4a, 0xc0, 0x6f, 0xd8, 0x5d, 0x6b, 0xca, 0xa4, 0xcd, 0x81, 0xf3, 0x2d, 0x1b,
    ],
    [
        0x37, 0x8e, 0xe7, 0x67, 0xf1, 0x16, 0x31, 0xba, 0xd2, 0x13, 0x80, 0xb0, 0x04, 0x49, 0xb1, 0x7a,
        0xcd, 0xa4, 0x3c, 0x32, 0xbc, 0xdf, 0x1d, 0x77, 0xf8, 0x20, 0x12, 0xd4, 0x30, 0x21, 0x9f, 0x9b,
        0x5d, 0x80, 0xef, 0x9d, 0x18, 0x91, 0xcc, 0x86, 0xe7, 0x1d, 0xa4, 0xaa, 0x88, 0xe1, 0x28, 0x52,
        0xfa, 0xf4, 0x17, 0xd5, 0xd9, 0xb2, 0x1b, 0x99, 0x48, 0xbc, 0x92, 0x4a, 0xf1, 0x1b, 0xd7, 0x20,
    ],
];
```

Код:

```rust
fn key_schedule(keys: &mut [u8; 64], iter_index: usize) {
    transform_x(&keys.clone(), &C[iter_index], keys);
    transform_s(keys);
    transform_p(keys);
    transform_l(keys);
}
```

# E-преобразование

E-преобразование является частью функции сжатия, которую использует Стрибог. Здесь тоже уже нет чего-то особенного - мы просто используем, написанные ранее, преобразования. Как можно видеть, в этом преобразовании мы и перебираем все итерационные константы `C`.

Код:

```rust
fn transform_e(
    keys: &mut [u8; 64],
    block: &[u8; 64],
    state: &mut [u8; 64]
) {
    transform_x(&block, &keys, state);

    for i in 0..12 {
        transform_s(state);
        transform_p(state);
        transform_l(state);
        key_schedule(keys, i);
        transform_x(&state.clone(), &keys, state);
    }
}
```

# Функция сжатия g

Наконец-то! Это последняя необходимая функция, прежде чем мы приступим уже к вычислению хэш-суммы. Как можно видеть, здесь мы объявляем и инициализируем нулями наши раундовые ключи `keys`.

Код:

```rust
fn transform_g(
    n: &[u8; 64],
    hash: &mut [u8; 64],
    message: &[u8; 64],
) {
    let mut keys = [0u8; 64];
    let mut temp = [0u8; 64];

    transform_x(n, hash, &mut keys);

    transform_s(&mut keys);
    transform_p(&mut keys);
    transform_l(&mut keys);

    transform_e(&mut keys, message, &mut temp);

    transform_x(&temp.clone(), hash, &mut temp);
    transform_x(&temp, &message, hash);
}
```

# Общая функция вычисления хэш-функции Стрибог

У обоих версий Стрибог одинаковый алгоритм вычисления хэша, разница заключается только в инициализации хэш-суммы и взятии нужной ее части на выходе.

Мы должны инициализировать два вспомогательных массива `N` и `Sigma`:

```rust
let mut n = [0u8; 64];
let mut sigma = [0u8; 64];
```

Для того, чтобы не расписывать портянку кода для полных и не полных блоков заранее выделим место под сам блок и размер полезных данных блока:

```rust
let mut block_size = [0u8; 64];
let mut block: [u8; 64];
```

В `block` мы будем копировать содержимое каждого очередного блока данных, размер которого равен 512 бит. А в `block_size` мы будем записывать размер полезных данных блока в битах.
Представим, что у вас есть данные ровно на два блока, то есть 1024 бита. Тогда в обоих случаях `block_size` будет хранить число 512. Думаю тут все ясно.

![Размер блока полных данных](assets/12.png)

Теперь представим, что данных у нас меньше, чем на два блока, например 816 бит. Тогда в первой итерации `block_size` будет хранить 512, а в следующий раз уже 304.
Интересная особенность заключается в том, что для хранения `block_size` отводится 64 байта. То есть каждый раз нам нужно будет изменять содержимое только для 2 из 64 байт.

![Размер блока данных](assets/13.png)

Соответственно, с помощью метода `chunks` мы разобьем наши данные на куски по 64 байта. Важно отметить, что если длина данных не кратна 64, то последняя часть будет меньше, чем 64 байта.

```rust
for chunk in message.chunks(64) {
    ...
}
```

Для каждого куска данных мы вычисляем размер полезных данных блока по уже приведенному выше алгоритму:

```rust
let chunk_size = chunk.len() as u16 * 8;
block_size[62..].copy_from_slice(&chunk_size.to_be_bytes());
```

Очевидно, что зачастую вы вряд ли будете получать данные, длина которых кратна 64 байтам. Поэтому мы будем дополнять необходимые блоки. Это очень простой алгоритм:

1.  Создаем блок, заполненный нулями.
2.  Копируем в него данные, которые у нас есть.
3.  После данных добавляем единицу.

![Заполнение блока](assets/14.png)

```rust
if chunk.len() != 64 {
    block = [0u8; 64];
    block[..chunk.len()].copy_from_slice(chunk);
    block[chunk.len()] = 1;
} else {
    ...
}
```

После всех манипуляций с данными блока, его необходимо развернуть:

```rust
block.reverse();
```

Вообще, здесь такая же ситуация как и с массивом констант `A`. Первый блок находится "в конце", а последний "в начале". По-хорошему мы должны дополнять сообщение как описано, однако на тестах все работает правильно и следовательно это равноправные операции дополнения.

Теперь, когда у нас есть данные, поделенные на блоки с дополнением, мы можем начать вычисление хэш-суммы. Когда хэш-сумма будет посчитана, ее тоже необходимо развернуть.

Код:

```rust
fn streebog_core(message: &[u8], hash: &mut [u8; 64]) {
    let mut n = [0u8; 64];
    let mut sigma = [0u8; 64];

    // Массив, хранящий размер полезных данных блока
    let mut block_size = [0u8; 64];
    let mut block: [u8; 64];

    for chunk in message.chunks(64) {
        // Вычисление размера полезных данных блока
        let chunk_size = chunk.len() as u16 * 8;
        block_size[62..].copy_from_slice(&chunk_size.to_be_bytes());

        // Дополнение блока
        if chunk.len() != 64 {
            block = [0u8; 64];
            block[..chunk.len()].copy_from_slice(chunk);
            block[chunk.len()] = 1;
        } else {
            block = chunk.try_into().unwrap();
        }
        block.reverse();

        transform_g(&n, hash, &block);
        add_512(&n.clone(), &block_size, &mut n);
        add_512(&sigma.clone(), &block, &mut sigma);
    }

    transform_g(&[0u8; 64], hash, &mut n);
    transform_g(&[0u8; 64], hash,&mut sigma);

    hash.reverse();
}
```

# Стрибог 512 и 256

Отличие, как и было сказано, заключается в двух моментах:

1.  Инициализация хэш-суммы.
2.  Выбор необходимой части.

Для 512 битной версии хэш-сумма инициализируется нулями:

```rust
let mut hash = [0u8; 64];
```

А для 256 битной версии единицами:

```rust
let mut hash = [1u8; 64];
```

При этом 512 битная версия возвращает хэш-сумму полностью, а 256 битная версия только последние 32 байта.

Код 512 битной версии:

```rust
pub fn streebog_512(message: &[u8]) -> [u8; 64] {
    let mut hash = [0u8; 64];

    streebog_core(message, &mut hash);

    hash
}
```

Код 256 битной версии:

```rust
pub fn streebog_256(message: &[u8]) -> [u8; 32] {
    let mut hash = [1u8; 64];

    streebog_core(message, &mut hash);

    hash[32..].try_into().unwrap()
}
```

# Опыт использования Perf

Как и SHA, Стрибог должен был пройти тесты, чтобы я мог убедиться в том, что он отрабатывает верно. В ходе тестов было выявлено, что этот код очень долго, порядка 10 секунд в `Debug` сборке и 1 секунды в `Release` сборке, вычисляет хэш-сумму для ~4MiB видео файла.
С помощью поиска получилось понять, что необходимо использовать профилировщик, чтобы попытаться найти бутылочные горлышки этого кода. Спойлер: ускорить не вышло.

![perf](assets/15.png)

`Perf` показал, что 25% времени выполнения программы на себя забирает `L` преобразование, однако я не нашел способов ускорить его. Во многих источниках было написано, что можно произвести некоторые приготовления к рассчету хэш-суммы, заранее вычислив все возможные варианты, однако это не наш метод.
Используя свой предыдущий опыт и чрезвычайно полезные советы из прошлого поста у меня получилось оптимизировать код до этого состояния.

Как натравить профилировщик на программу:

1.  `cargo build`
2.  `perf record -g ./target/debug/hand-made-streebog`
3.  `perf report`

# Заключение

Пишу статью второй раз, конечно же где-то могут быть неточности и ошибки. Как и пост про SHA, это записка для студентов и тех, кто просто интересуется. Как и в прошлый раз я надеюсь на конструктивную критику со стороны более опытных программистов.

Любые правки, советы, исправления готов рассмотреть и внести при необходимости. Это можно сделать как в комментариях, так и в [репозитории GitVerse](https://gitverse.ru/digit4lsh4d0w/cryptography/content/main/hand-made-streebog).

Еще бы я хотел написать здесь про ключевую хэш-функцию HMAC. Напишите комментарии (или поставьте реакции) если бы хотели такой материал.

[![banner_v2](assets/banner.png)](https://t.me/digit4lsh4d0w_channel)
[Анонсы и чат в телеграм](https://t.me/digit4lsh4d0w_channel).

# Источники

- [WikiPedia](https://ru.wikipedia.org/wiki/%D0%A1%D1%82%D1%80%D0%B8%D0%B1%D0%BE%D0%B3_%28%D1%85%D0%B5%D1%88-%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F%29 "https://ru.wikipedia.org/wiki/%D0%A1%D1%82%D1%80%D0%B8%D0%B1%D0%BE%D0%B3_(%D1%85%D0%B5%D1%88-%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F)"). Спецификации и описание.
- [Habr](https://habr.com/ru/articles/188152/). Псевдокод, C# код, начальные и промежуточные значения.
- [Хакер](https://xakep.ru/2016/07/20/hash-gost-34-11-2012/). C код, начальные значения для SHA512.
- [Cypherpunks Web](http://www.gost.cypherpunks.ru/Russian.html). Сравнительная таблица Российских и Западных крипто-протоколов. Есть ссылки для каждого примера.
- [Cypherpunks Git](http://www.git.cypherpunks.ru/). Веб-обертка для git репозиториев, где можно найти несколько, посвященных Российским крипто-протоколам, проектов.
- [GitHub](https://github.com/drobotun/stribog/). C код.
- [GitHub](https://github.com/okazymyrov/stribog/). C код.
- [Hashing Tools](https://hashing.tools/streebog/). Проверка хэш-сумм.